// https://soj.turingedu.cn/problem/60700/

int n, m;
vector<int> adj[maxn];

int dfn_cnt, dfn[maxn], low[maxn];
int scc_cnt, id[maxn]; // 第几个连通分量
int top, path[maxn];   // dfs 路径
void dfs(int u) {
    dfn[u] = low[u] = ++dfn_cnt, path[++top] = u;
    for (auto v : adj[u]) {
        if (!dfn[v]) { // 未访问过，树边
            dfs(v);
            low[u] = min(low[u], low[v]);
        } else if (!id[v]) { // 访问过且在路径栈中，返祖边
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (dfn[u] == low[u]) { // u 是强连通分量的起点
        scc_cnt++;
        for (; path[top] != u; top--) {
            id[path[top]] = scc_cnt;
        }
        id[path[top--]] = scc_cnt;
    }
}
